发现环

题目 发现环

思路分析

发现忘了怎么存图 直觉告诉是用并查集 但是也是忘了咋用emmm 好 该复习的点找到了

因为这条路卡住了 就想着换一个方式解决 用快慢指针的方式 遍历图构造链表 再在链表中使用快慢指针判断是否有环 但由于链表是单后继 图是多后继 要这样做就只能把每种情况都拆分开来构造一个链表再做 显然耗时耗力

再或者直接用bfs遍历树 记录每个节点的父节点是谁 当访问到一个已经访问过的节点时 就是发现环 接着回溯父节点找到环的组成

回头再看吧 这题留着复习后自检用

代码实现

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 100005;
const int MAX_EDGES = 200010;

int head[MAX_N], to[MAX_EDGES], nxt[MAX_EDGES], ecnt;
int parent[MAX_N], visited[MAX_N];
vector<int> cycle;

void add_edge(int u, int v) {
    to[ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt++;
}

void find_cycle(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = 1;
    parent[start] = -1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (!visited[v]) {
                visited[v] = 1;
                parent[v] = u;
                q.push(v);
            } else if (parent[u] != v) {
                // 发现环
                set<int> unique_nodes;
                int cur = u;
                while (cur != -1 && unique_nodes.find(cur) == unique_nodes.end()) {
                    unique_nodes.insert(cur);
                    cur = parent[cur];
                }
                cur = v;
                while (cur != -1 && unique_nodes.find(cur) == unique_nodes.end()) {
                    unique_nodes.insert(cur);
                    cur = parent[cur];
                }
                cycle.assign(unique_nodes.begin(), unique_nodes.end());
                return;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    fill(head, head + MAX_N, -1);
    ecnt = 0;

    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    memset(visited, 0, sizeof visited);
    find_cycle(1);

    sort(cycle.begin(), cycle.end());

    for (int node : cycle) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

同类题型

视频讲解

⬅️ 希尔伯特曲线 🏠 00-冲刺国赛 ➡️ 对局匹配